type Handler = {
    function: (...args: any) => any;
    context: object;
};

type HandlerTable = {
    [key in "POST" | "GET" | "PUT" | "DELETE" | "HEAD"]?: Handler;
};

class Node {
    step: Step;
    handlerTable?: HandlerTable;
    children: Node[] = [];

    constructor(step: Step, handlerTable?: HandlerTable) {
        this.step = step;
        if (handlerTable) {
            this.handlerTable = handlerTable;
        }
    }

    static from(stepStr: string, handlerTable?: HandlerTable): Node {
        let step: Step;
        if (stepStr.startsWith("{") && stepStr.endsWith("}")) {
            stepStr = stepStr.slice(1, stepStr.length - 1);
            step = new ParamStep(stepStr);
        } else {
            step = new StringStep(stepStr);
        }

        return new Node(step, handlerTable);
    }

    addChild(node: Node) {
        this.children?.push(node);
    }

    setHandler(method: keyof HandlerTable, handler: Handler) {
        if (this.handlerTable == undefined) {
            this.handlerTable = Object.create(null);
        }

        (this.handlerTable as HandlerTable)[method] = handler;
    }
}

interface Step {
    path: string;
    match(step: string): boolean;
    equal(step: string): boolean;
}

/**
 * 原始字符串路由
 */
class StringStep implements Step {
    path: string;
    constructor(pathNode: string) {
        this.path = pathNode;
    }
    match(path: string): boolean {
        return this.path === path;
    }

    equal(path: string): boolean {
        return this.match(path);
    }
}

/**
 * 参数路由，例如{id}、{name}
 */
class ParamStep implements Step {
    path: string;
    name: string;
    constructor(path: string) {
        this.path = path;
        this.name = path.slice(1, path.length - 1);
    }

    match(path: string): boolean {
        return path != "";
    }

    equal(path: string): boolean {
        return this.path === path;
    }
}

class Trie {
    root: Node;
    private pathParamCache: { [key: string]: string } = {};

    constructor() {
        this.root = new Node(new StringStep(""));
    }

    /**
     * 将路径和处理器作为新节点插入字典树
     * @param path 路径，例如/path/to/file/GET
     * @param handler 对应路径请求的处理器
     * @returns void
     */
    insertNode(path: string, method: keyof HandlerTable, handler: Handler) {
        if (path === "/") {
            if (this.root.handlerTable == undefined) {
                this.root.handlerTable = Object.create(null);
            }
            (this.root.handlerTable as HandlerTable)[method] = handler;

            return;
        }

        let stepStrings = path.split("/"); // 结果为 ['', 'xx',...]

        // 从根节点开始寻找插入点
        let p: Node = this.root;
        let i = 1; // 因为路径第一步肯定等于根节点，所以跳过i=0
        for (; i < stepStrings.length; i++) {
            let j = 0;
            for (; j < p.children.length; j++) {
                if (p.children[j].step.equal(stepStrings[i])) {
                    break;
                }
            }
            // 如果 j 为 子节点列表的长度值，说明遍历完当前节点的子节点也没找到和当前步骤匹配的节点
            if (j == p.children.length) {
                break;
            } else {
                p = p.children[j];
            }
        }
        // 找到插入节点 p，应该插到 p 节点的子节点列表中
        for (; i < stepStrings.length; i++) {
            // 先创建节点，才能插入
            let node;
            if (
                stepStrings[i].startsWith("{") &&
                stepStrings[i].endsWith("}")
            ) {
                node = new Node(new ParamStep(stepStrings[i]));
            } else {
                node = new Node(new StringStep(stepStrings[i]));
            }
            p.children.push(node);
            p = node;
        }
        // 最后别忘了设置handler
        p.setHandler(method, handler);
    }

    /**
     * 寻找和路径匹配的节点
     * @param path 路由路径
     * @returns
     */
    find(path: string): Node | null {
        if (path === "/") {
            return this.root;
        }
        this.pathParamCache = {};
        let steps = path.split("/");
        return this._dft(steps, 0, this.root);
    }

    popPathParams(): { [key: string]: string } {
        let params = this.pathParamCache;
        this.pathParamCache = {};
        return params;
    }

    /**
     * 在 Trie 中深度优先搜索匹配的路径
     * @param steps 路径列表
     * @param i 当前路径下标
     * @param p 当前遍历到的 Trie 节点
     * @returns 成功搜索到就返回匹配的节点，否则返回 null
     */
    private _dft(steps: string[], i: number, p: Node): Node | null {
        if (i >= steps.length) {
            return null;
        }

        if (p.step.match(steps[i])) {
            if (p.step instanceof ParamStep) {
                this.pathParamCache[p.step.name] = steps[i];
            }
            if (i === steps.length - 1) {
                return p;
            } else {
                if (p.children.length === 0) {
                    return null;
                } else {
                    for (let q of p.children) {
                        let node = this._dft(steps, i + 1, q);
                        if (node !== null) {
                            return node;
                        }
                    }
                    if (p.step instanceof ParamStep) {
                        delete this.pathParamCache[p.step.name];
                    }
                    return null;
                }
            }
        } else {
            return null;
        }
    }
}

export { Node, Step, StringStep, ParamStep, Trie, HandlerTable, Handler };
